package leetcode.editor.cn.dsa22_segmentTree;
//请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
//
// 1. add(int num) 
// 将数字 num 添加到当前数字列表的最后面。
// 
// 2. getProduct(int k)
// 返回当前数字列表中，最后 k 个数字的乘积。
// 你可以假设当前列表中始终 至少 包含 k 个数字。 
//
// 题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。 
//
// 示例： 
// 输入：
//["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","g
//etProduct","add","getProduct"]
//[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
//
//输出：
//[null,null,null,null,null,null,20,40,0,null,32]
//
//解释：
//ProductOfNumbers productOfNumbers = new ProductOfNumbers();
//productOfNumbers.add(3);        // [3]
//productOfNumbers.add(0);        // [3,0]
//productOfNumbers.add(2);        // [3,0,2]
//productOfNumbers.add(5);        // [3,0,2,5]
//productOfNumbers.add(4);        // [3,0,2,5,4]
//productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
//productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
//productOfNumbers.getProduct(4); // 返回  0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
//productOfNumbers.add(8);        // [3,0,2,5,4,8]
//productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32 
//
// 提示： 
// add 和 getProduct 两种操作加起来总共不会超过 40000 次。
// 0 <= num <= 100 
// 1 <= k <= 40000 
// 
// Related Topics 设计 数组 
// 👍 50 👎 0

import java.util.ArrayList;
import java.util.List;

public class ProductOfTheLastKNumbers1352_1 {
    public static void main(String[] args) {
        ProductOfNumbers obj = new ProductOfTheLastKNumbers1352_1().new ProductOfNumbers();
        obj.add(3);obj.add(0);obj.add(0);obj.add(8);obj.add(3);
        System.out.println(obj.getProduct(1)); //3
        obj.add(7);
        System.out.println(obj.getProduct(5)); //0
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class ProductOfNumbers {
        List<Integer> list; // 存储前缀乘积
        int zeroIndex = -1; // 记录最后一次出现 0 的索引
        public ProductOfNumbers() {
            list = new ArrayList<>();
            list.add(1); // 初始化一个元素，方便计算
        }

        // 3 0 0 8 3，我们记录的数组为 [1,3,1,1,8,24]
        public void add(int num) {
            if (num == 0) { // 遇到 0 记录索引，存储1
                zeroIndex = list.size();
                list.add(1);
            } else { // 累计乘积值
                list.add(num * list.get(list.size() - 1));
            }
        }

        public int getProduct(int k) {
            int size = list.size();
            // 判断k包含的区间是否有0
            if (zeroIndex >= size - k && zeroIndex <= size - 1) return 0;
            return list.get(size - 1) / list.get(size - 1 - k);
        }
    }

    /**
     * Your ProductOfNumbers object will be instantiated and called as such:
     * ProductOfNumbers obj = new ProductOfNumbers();
     * obj.add(num);
     * int param_2 = obj.getProduct(k);
     */
    //leetcode submit region end(Prohibit modification and deletion)
}